package com.company.test24;


import java.util.ArrayList;

/**
 * Created by Administrator on 2016.10.18.
 */
public class Heap<E extends Comparable<E>> {
    private ArrayList<E> list=new ArrayList<E>();

    public Heap(){

    }

    public Heap(E[] objects){
        for(int i=0;i<objects.length;i++){
            add(objects[i]);
        }
    }

    public void add(E newObject){
        list.add(newObject);
        int currentIndex=list.size()-1;

        while (currentIndex>0){
            int parentIndex=(currentIndex-1)/2;

            if(list.get(parentIndex).compareTo(list.get(currentIndex))<0){
                E e=list.get(parentIndex);
                list.set(parentIndex,list.get(currentIndex));
                list.set(currentIndex,e);
            }else{
                break;
            }

            currentIndex=parentIndex;
        }

    }

    public E remove(){
        if(list.size()==0)
            return null;

        E removeObject=list.get(0);

        list.set(0,list.get(list.size()-1));
        list.remove(list.size()-1);

        int currentIndex=0;

        while (currentIndex<list.size()){
            int leftChildIndex=currentIndex*2+1;
            int rightChildIndex=currentIndex*2+2;

            if(leftChildIndex>=list.size()){
                break;
            }

            int maxChildIndex=leftChildIndex;
            if(rightChildIndex<list.size()
                    &&list.get(rightChildIndex).compareTo(list.get(leftChildIndex))>0){
                maxChildIndex=rightChildIndex;
            }

            if(list.get(currentIndex).compareTo(list.get(maxChildIndex))<0){
                E e=list.get(maxChildIndex);
                list.set(maxChildIndex,list.get(currentIndex));
                list.set(currentIndex,e);
                currentIndex=maxChildIndex;
            }else {
                break;
            }
        }
        return removeObject;
    }

    public int size(){
        return list.size();
    }
}
